const MGraph = require('./邻接表')

/**
 * 深度优先遍历
 * @param {*} g 图
 * @param {*} v 顶点下标
 */

const g = new MGraph(['A', 'B', 'C', 'D'], [{i: 0, j: 1, wei: 10}, {i: 0, j: 3, wei: 30}, {i: 1, j: 3, wei: 20}, {i: 3, j: 2, wei: 40}, {i: 2, j: 0, wei: 50}], '2')

 const visited = []
 for (let i = 0; i < g.data.length; i++) {
     visited[i] = 0
 }

function dfs(g, v) {
    console.log(g.data[v].data)
    visited[v] = 1
    let w = firstadj(g, v)
    
    while(w !== null) {
        if(visited[w] === 0) {
            dfs(g, w)
        }        
        w = nextadj(g, v, w)
    }
}

/**
 * 邻接表中获取图g中顶点表中下标为v的第一条边
 * 存在的话返在边中的下标信息，否则返回null
 * @param {*} g 图
 * @param {*} v 弧尾顶点
 */
function firstadj(g, v) {
    const e = g.data[v].firstEdge
    if (e) {
        return e.index
    } else {
        return null
    }
}

/**
 * 邻接表中获取图g中顶点表中下标为v的链表中链表节点属性index == w节点的下一个节点
 * 有返回 该节点的 index属性值，否则返回 null
 * @param {*} g 图
 * @param {*} v 弧尾顶点
 * @param {*} w 前一个顶点的下标
 */
function nextadj(g, v, w) {
    let e = g.data[v].firstEdge
    
    while (e | e.index != w) {
        e = e.nextCNode
    }
    if (e && e.nextCNode) {
        return e.nextCNode.index
    } else {
        return null
    }
}

dfs(g, 0)